package com.mlh.greed;

/**
 * @author 缪林辉
 * @date 2024/4/16 10:26
 * @DESCRIPTION
 */
// 当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
// 给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
// 示例 2:
// 输入: n = 1234
// 输出: 1234
// 示例 3:
// 输入: n = 332
// 输出: 299
public class 单调递增的数字 {
    //贪心策略：局部前一位如果大于后一位，那么只能高位-1，后一位选9
    //推广到全局的话 从前向后遍历，找到第一个前一位大于后一位的下标，前一位-1，后面的全部变为9
    //但是这样可能会导致前一位-1之后会小于前一位的前一位，因此需要在第一次遍历的结果上从后向前遍历，如果前一位大于后一位，高位-1，后一位选9
    public static int method1(int n) {
        String s= Integer.toString(n);
        char[] chars = s.toCharArray();
        int index=-1;
        //找到第一个前一位大于后一位的下标
        for (int i = 0; i <chars.length-1; i++) {
            if(chars[i]>chars[i+1]){
                index=i;
                break;
            }
        }
        if(index==-1){
            return n;
        }else{
            //前一位-1
            chars[index]--;
        }
        //后面的全部变为9
        for (int i = index+1; i < chars.length; i++) {
            chars[i]='9';
        }
        //从后向前遍历，如果前一位大于后一位，高位-1，后一位选9
        for (int i = index; i >0 ; i--) {
            if(chars[i]<chars[i-1]){
                chars[i]='9';
                chars[i-1]--;
            }
        }
        String s1 = String.valueOf(chars);
        return Integer.valueOf(s1);
    }

    public static void main(String[] args) {
        int i = method1(989998);
        System.out.println(i);
    }
}